package com.zjw.algorithm.ready1;

import java.util.List;

public class _最大合金数 {

    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int l = 0;
        int r = budget / stock.get(0) + stock.get(0);
        int ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (isValid(n, k, budget, composition, stock, cost, mid)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return ans;
    }

    private boolean isValid(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost, int mid) {

        for (int i = 0; i < k; i++) {
            List<Integer> list = composition.get(i);
            int spend = 0;
            for (int j = 0; j < n; ++j) {
                spend += Math.max((long) list.get(j) * mid - stock.get(j), 0) * cost.get(j);
            }

            if (spend <= budget) {
                return true;
            }
        }
        return false;
    }
}
